package greedy;

public class JumpGameii45 {

    //todo use greedy

//    public int jump2(int[] nums) {
//        int step = 0;
//        int scope = nums[0];
//        int nextScope = nums[0];
//        int index = 0;
//        while (nextScope<nums.length){
//            while (index<scope){
//                if()
//
//            }
//
//
//        }
//
//
//    }

    public int jump(int[] nums) {
        int[] steps = new int[nums.length];
        steps[0] = 0;
        for (int i = 0; i < nums.length; i++) {
            int len = nums[i];
            for (int j = 1; j < len + 1; j++) {
                if (i + j < nums.length && steps[i + j] == 0) {
                    steps[i + j] = steps[i] + 1;
                }
                if (i + j < nums.length && steps[i + j] > steps[i] + 1) {
                    steps[i + j] = steps[i] + 1;
                }
            }
        }
        return steps[nums.length - 1];
    }
}
